package com.zx._12_算法.数据结构.link;

/**
 * @version v1.0
 * @Project: knowledge
 * @Title: Demo3
 *         翻转链表（困难模式）
 * @author: zhangxue
 * @date: 2019年7月27日下午8:34:11
 * @company: 未知之地
 * @Copyright: Copyright (c) 2019
 */
public class Demo3 {

    public static void main(String[] args) {
        Node<String> node1 = new Node<>();
        Node<String> node2 = new Node<>();
        Node<String> node3 = new Node<>();
        Node<String> node4 = new Node<>();
        Node<String> node5 = new Node<>();

        node1.data = "1";
        node1.next = node2;
        node2.data = "2";
        node2.next = node3;
        node3.data = "3";
        node3.next = node4;
        node4.data = "4";
        node4.next = node5;
        node5.data = "5";

        Node<String> reverse = reverse2(node1);
        Node<String> node = reverse;
        while (node != null) {
            System.out.println(node.data);
            node = node.next;
        }
    }

    /**
     * 方式1：使用迭代的方式获得翻转
     */
    public static Node<String> reverse1(Node<String> head) {
        Node<String> currNode = head;            // 节点1
        Node<String> currNextNode = head.next;        // 节点2
        currNode.next = null;                            // 手动将节点1的next置为null

        while (currNextNode != null) {
            Node<String> nextNode = currNextNode;    // 节点2
            Node<String> nextNextNode = nextNode.next;    // 节点3， 下面不对节点3操作
            // 将节点2的 next转为 节点1
            nextNode.next = currNode;
            // 开始下一轮的遍历
            currNode = nextNode;
            currNextNode = nextNextNode;
        }

        return currNode;
    }

    /**
     * 方式2：使用递归的方式获得翻转
     */
    public static Node<String> reverse2(Node<String> head) {
        // 假设head为节点1
        if (head.next == null) {
            return head;
        }

        // 获得最后一个节点为新的节点1
        Node<String> newNode = reverse2(head.next);

        head.next.next = head;// 将 旧的节点2的next指向旧的节点1
        head.next = null;// 旧的节点1的next为null

        return newNode;
    }

    static class Node<T> {

        T data;
        Node<T> next;
    }
}
